package _2022.hot100._208_实现前缀树_2;

/** 字典树
 * @author： YHSimon
 * @date： 2022-05-14 16:12
 */
public class Trie {
    private Trie[] children;
    private boolean isEnd;

    public Trie(){
        children=new Trie[26];
        isEnd=false;
    }

    public void insert(String word){
        Trie node=this;
        for(int i=0;i<word.length();i++){
            char ch=word.charAt(i);
            int index=ch-'a';
            if(node.children[index]==null){
                node.children[index]=new Trie();
            }
            node=node.children[index];
        }
        node.isEnd=true;
    }

    public boolean search(String word){
        Trie node=searchPrefix(word);
        return node!=null&&node.isEnd;
    }

    public Trie searchPrefix(String prefix){
        Trie node=this;
        for(int i=0;i<prefix.length();i++){
            char ch=prefix.charAt(i);
            int index=ch-'a';
            if(node.children[index]==null){
                return null;
            }
            node=node.children[index];
        }
        return node;
    }

    public boolean startsWith(String prefix){
        return searchPrefix(prefix)!=null;
    }


    public static void main(String[] args) {

    }
}
